home *** CD-ROM | disk | FTP | other *** search
/ IRIX Base Documentation 2001 May / SGI IRIX Base Documentation 2001 May.iso / usr / share / catman / p_man / cat3 / btree.z / btree
Encoding:
Text File  |  1998-10-20  |  10.9 KB  |  265 lines
  1.  
  2.  
  3.  
  4.      BBBBTTTTRRRREEEEEEEE((((3333))))         UUUUNNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((AAAAuuuugggguuuusssstttt 11118888,,,, 1111999999994444))))         BBBBTTTTRRRREEEEEEEE((((3333))))
  5.  
  6.  
  7.  
  8.      NNNNAAAAMMMMEEEE
  9.           btree - btree database access method
  10.  
  11.      SSSSYYYYNNNNOOOOPPPPSSSSIIIISSSS
  12.           ####iiiinnnncccclllluuuuddddeeee <<<<ssssyyyyssss////ttttyyyyppppeeeessss....hhhh>>>>
  13.           ####iiiinnnncccclllluuuuddddeeee <<<<ddddbbbb....hhhh>>>>
  14.  
  15.      DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
  16.           The routine _d_b_o_p_e_n is the library interface to database
  17.           files.  One of the supported file formats is btree files.
  18.           The general description of the database access methods is in
  19.           _d_b_o_p_e_n(3), this manual page describes only the btree
  20.           specific information.
  21.  
  22.           The btree data structure is a sorted, balanced tree
  23.           structure storing associated key/data pairs.
  24.  
  25.           The btree access method specific data structure provided to
  26.           _d_b_o_p_e_n is defined in the <db.h> include file as follows:
  27.  
  28.           typedef struct {
  29.                u_long flags;
  30.                u_int cachesize;
  31.                int maxkeypage;
  32.                int minkeypage;
  33.                u_int psize;
  34.                int (*compare)(const DBT *key1, const DBT *key2);
  35.                size_t (*prefix)(const DBT *key1, const DBT *key2);
  36.                int lorder;
  37.           } BTREEINFO;
  38.  
  39.           The elements of this structure are as follows:
  40.  
  41.           flags
  42.                The flag value is specified by _o_r'ing any of the
  43.                following values:
  44.  
  45.                R_DUP
  46.                     Permit duplicate keys in the tree, i.e. permit
  47.                     insertion if the key to be inserted already exists
  48.                     in the tree.  The default behavior, as described
  49.                     in _d_b_o_p_e_n(3), is to overwrite a matching key when
  50.                     inserting a new key or to fail if the
  51.                     R_NOOVERWRITE flag is specified.  The R_DUP flag
  52.                     is overridden by the R_NOOVERWRITE flag, and if
  53.                     the R_NOOVERWRITE flag is specified, attempts to
  54.                     insert duplicate keys into the tree will fail.
  55.  
  56.                     If the database contains duplicate keys, the order
  57.                     of retrieval of key/data pairs is undefined if the
  58.                     _g_e_t routine is used, however, _s_e_q routine calls
  59.                     with the R_CURSOR flag set will always return the
  60.  
  61.  
  62.  
  63.      Page 1                                          (printed 4/30/98)
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.      BBBBTTTTRRRREEEEEEEE((((3333))))         UUUUNNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((AAAAuuuugggguuuusssstttt 11118888,,,, 1111999999994444))))         BBBBTTTTRRRREEEEEEEE((((3333))))
  71.  
  72.  
  73.  
  74.                     logical ``first'' of any group of duplicate keys.
  75.  
  76.           cachesize
  77.                A suggested maximum size (in bytes) of the memory
  78.                cache.  This value is oooonnnnllllyyyy advisory, and the access
  79.                method will allocate more memory rather than fail.
  80.                Since every search examines the root page of the tree,
  81.                caching the most recently used pages substantially
  82.                improves access time.  In addition, physical writes are
  83.                delayed as long as possible, so a moderate cache can
  84.                reduce the number of I/O operations significantly.
  85.                Obviously, using a cache increases (but only increases)
  86.                the likelihood of corruption or lost data if the system
  87.                crashes while a tree is being modified.  If _c_a_c_h_e_s_i_z_e
  88.                is 0 (no size is specified) a default cache is used.
  89.  
  90.           maxkeypage
  91.                The maximum number of keys which will be stored on any
  92.                single page.  Not currently implemented.
  93.  
  94.           minkeypage
  95.                The minimum number of keys which will be stored on any
  96.                single page.  This value is used to determine which
  97.                keys will be stored on overflow pages, i.e. if a key or
  98.                data item is longer than the pagesize divided by the
  99.                minkeypage value, it will be stored on overflow pages
  100.                instead of in the page itself.  If _m_i_n_k_e_y_p_a_g_e is 0 (no
  101.                minimum number of keys is specified) a value of 2 is
  102.                used.
  103.  
  104.           psize
  105.                Page size is the size (in bytes) of the pages used for
  106.                nodes in the tree.  The minimum page size is 512 bytes
  107.                and the maximum page size is 64K.  If _p_s_i_z_e is 0 (no
  108.                page size is specified) a page size is chosen based on
  109.                the underlying file system I/O block size.
  110.  
  111.           compare
  112.                Compare is the key comparison function.  It must return
  113.                an integer less than, equal to, or greater than zero if
  114.                the first key argument is considered to be respectively
  115.                less than, equal to, or greater than the second key
  116.                argument.  The same comparison function must be used on
  117.                a given tree every time it is opened.  If _c_o_m_p_a_r_e is
  118.                NULL (no comparison function is specified), the keys
  119.                are compared lexically, with shorter keys considered
  120.                less than longer keys.
  121.  
  122.           prefix
  123.                Prefix is the prefix comparison function.  If
  124.                specified, this routine must return the number of bytes
  125.                of the second key argument which are necessary to
  126.  
  127.  
  128.  
  129.      Page 2                                          (printed 4/30/98)
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.      BBBBTTTTRRRREEEEEEEE((((3333))))         UUUUNNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((AAAAuuuugggguuuusssstttt 11118888,,,, 1111999999994444))))         BBBBTTTTRRRREEEEEEEE((((3333))))
  137.  
  138.  
  139.  
  140.                determine that it is greater than the first key
  141.                argument.  If the keys are equal, the key length should
  142.                be returned.  Note, the usefulness of this routine is
  143.                very data dependent, but, in some data sets can produce
  144.                significantly reduced tree sizes and search times.  If
  145.                _p_r_e_f_i_x is NULL (no prefix function is specified), aaaannnndddd
  146.                no comparison function is specified, a default lexical
  147.                comparison routine is used.  If _p_r_e_f_i_x is NULL and a
  148.                comparison routine is specified, no prefix comparison
  149.                is done.
  150.  
  151.           lorder
  152.                The byte order for integers in the stored database
  153.                metadata.  The number should represent the order as an
  154.                integer; for example, big endian order would be the
  155.                number 4,321.  If _l_o_r_d_e_r is 0 (no order is specified)
  156.                the current host order is used.
  157.  
  158.           If the file already exists (and the O_TRUNC flag is not
  159.           specified), the values specified for the parameters flags,
  160.           lorder and psize are ignored in favor of the values used
  161.           when the tree was created.
  162.  
  163.           Forward sequential scans of a tree are from the least key to
  164.           the greatest.
  165.  
  166.           Space freed up by deleting key/data pairs from the tree is
  167.           never reclaimed, although it is normally made available for
  168.           reuse.  This means that the btree storage structure is
  169.           grow-only.  The only solutions are to avoid excessive
  170.           deletions, or to create a fresh tree periodically from a
  171.           scan of an existing one.
  172.  
  173.           Searches, insertions, and deletions in a btree will all
  174.           complete in O lg base N where base is the average fill
  175.           factor.  Often, inserting ordered data into btrees results
  176.           in a low fill factor.  This implementation has been modified
  177.           to make ordered insertion the best case, resulting in a much
  178.           better than normal page fill factor.
  179.  
  180.      EEEERRRRRRRROOOORRRRSSSS
  181.           The _b_t_r_e_e access method routines may fail and set _e_r_r_n_o for
  182.           any of the errors specified for the library routine
  183.           _d_b_o_p_e_n(3).
  184.  
  185.      SSSSEEEEEEEE AAAALLLLSSSSOOOO
  186.           _d_b_o_p_e_n(3), _h_a_s_h(3), _m_p_o_o_l(3), _r_e_c_n_o(3)
  187.  
  188.           _T_h_e _U_b_i_q_u_i_t_o_u_s _B-_t_r_e_e, Douglas Comer, ACM Comput. Surv. 11,
  189.           2 (June 1979), 121-138.
  190.  
  191.           _P_r_e_f_i_x _B-_t_r_e_e_s, Bayer and Unterauer, ACM Transactions on
  192.  
  193.  
  194.  
  195.      Page 3                                          (printed 4/30/98)
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.      BBBBTTTTRRRREEEEEEEE((((3333))))         UUUUNNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((AAAAuuuugggguuuusssstttt 11118888,,,, 1111999999994444))))         BBBBTTTTRRRREEEEEEEE((((3333))))
  203.  
  204.  
  205.  
  206.           Database Systems, Vol. 2, 1 (March 1977), 11-26.
  207.  
  208.           _T_h_e _A_r_t _o_f _C_o_m_p_u_t_e_r _P_r_o_g_r_a_m_m_i_n_g _V_o_l. _3: _S_o_r_t_i_n_g _a_n_d
  209.           _S_e_a_r_c_h_i_n_g, D.E. Knuth, 1968, pp 471-480.
  210.  
  211.      BBBBUUUUGGGGSSSS
  212.           Only big and little endian byte order is supported.
  213.  
  214.           This version of berkeley db (1.85) is free software which is
  215.           not developed nor maintained by SGI.  It is known to have
  216.           some bugs that are unlikely to get fixed (See NOTES below)
  217.           in particular, the following btree operations are known to
  218.           have problems, up to corrupting databases, and should be
  219.           avoided according to http://www.sleepycat.com/db.185.html:
  220.  
  221.             o  Btree cursor (seq) operations.
  222.  
  223.             o  Large numbers of btree duplicates (specifically,
  224.                migrating duplicate keys into internal pages).
  225.  
  226.             o  Large numbers of btree deletes (you should periodically
  227.                dump and rebuild the database if you delete large
  228.                numbers of records).
  229.  
  230.  
  231.      NNNNOOOOTTTTEEEESSSS
  232.           This version of berkeley db is 1.85.  A newer enhanced
  233.           version db-2.x requires licensing. Check out
  234.           http://www.sleepycat.com/ for details.
  235.  
  236.  
  237.  
  238.  
  239.  
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261.      Page 4                                          (printed 4/30/98)
  262.  
  263.  
  264.  
  265.